home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / point_set.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  4.1 KB  |  107 lines
  1. {\magonebf  6.3 Sets of two-dimensional points (point\_set)}
  2.  
  3. \decl point\_set I
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $S$ of the parameterized data type \name\ is a collection 
  8. of items ($ps\_item$). Every item in $S$ contains a two-dimensional point as 
  9. key (data type $point$), and an information from data type $I$, called 
  10. the information type of $S$. The number of items in $S$ is called the size of 
  11. $S$. A point set of size zero is said to be empty. We use $<p,i>$ to denote the 
  12. item with point $p$, and information $i$. For each  point $p$ there is at most 
  13. one item $<p,i> \in S$. Beside the normal dictionary operations, the data
  14. type $point\_set$ provides operations for rectangular range queries and
  15. nearest neighbor queries. 
  16.  
  17.  
  18.  
  19. \bigskip
  20. {\bf 2. Creation}
  21.  
  22. \create S {}
  23.  
  24. creates an instance \var\ of type \name\ and initializes \var\ to the 
  25. empty set. 
  26.  
  27.  
  28.  
  29. \bigskip
  30. {\bf 3. Operations}
  31.  
  32. \+\cleartabs & \hskip 2.6truecm & \hskip 6truecm &\cr
  33. \+\op point          key {ps\_item\ it}   
  34.                       {returns the point of item $it$.}
  35. \+\nop                {\precond $it$ is an item in \var.}
  36. \smallskip
  37. \+\op I              inf {ps\_item\ it}   
  38.                       {returns the information of item $it$.}
  39. \+\nop                {\precond $it$ is an item in \var.}
  40. \smallskip
  41. \+\op ps\_item       insert {point\ p,\ I\ i} 
  42.                       {associates the information $i$ with point $p$.}
  43. \+\nop                {If there is an item $<p,j>$ in \var\ then $j$}
  44. \+\nop                {is replaced by $i$, else a new item $<p,i>$}
  45. \+\nop                {is added to $S$. In both cases the item is}
  46. \+\nop                {returned.}
  47. \smallskip
  48. \+\op ps\_item       lookup {point\ p} 
  49.                       {returns the item with point $p$ (nil if no}
  50. \+\nop                {such item exists in \var).}
  51. \smallskip
  52. \+\op ps\_item       nearest\_neighbor {point\ q}
  53.                       {returns the item $<p,i>\ \in\ S$ such that}
  54. \+\nop                {the distance between $p$ and $q$ is minimal.}
  55. \smallskip
  56. \+\op list\<ps\_item\> range\_search {double\ x_0,\ double\ x_1,\ double\ y_0,\ double\ y_1}  {}
  57. \+\nop                {returns all items $<p,i>\ \in\ S$ with}
  58. \+\nop                {$x_0 \le p$.xcoord() $\le x_1$ and}
  59. \+\nop                {$y_0 \le p$.ycoord() $\le y_1$}
  60. \smallskip
  61. \+\op list\<ps\_item\> convex\_hull {}
  62.                       {returns the list of items containing all}
  63. \+\nop                {points of the convex hull of \var\ in clock-}
  64. \+\nop                {wise order.}
  65. \smallskip
  66. \+\op void           del {point\ p}         
  67.                       {deletes the item with point $p$ from \var}
  68. \smallskip
  69. \+\op void           del\_item {ps\_item it}   
  70.                               {removes item $it$ from \var.}
  71. \+\nop                        {\precond $it$ is an item in \var.}
  72. \smallskip
  73. \+\op void           change\_inf {ps\_item\ it,\ I\ i} 
  74.                               {makes $i$ the information of item $it$.}
  75. \+\nop                        {\precond $it$ is an item in \var.}
  76. \smallskip
  77. \+\op list\<ps\_item\> all\_items {}
  78.                               {returns the list of all items in $S$. }
  79. \smallskip
  80. \+\op list\<point\>    all\_points {}
  81.                               {returns the list of all points in $S$. }
  82. \smallskip
  83. \+\op void           clear {} 
  84.                               {makes \var\ the empty point\_set.}
  85. \smallskip 
  86. \+\op bool           empty {} 
  87.                               {returns true iff \var\ is empty.}
  88. \smallskip 
  89. \+\op int            size {}  
  90.                               {returns the size of \var.}
  91.  
  92.  
  93.  
  94.  
  95. \bigskip
  96. {\bf 4. Implementation}
  97.  
  98. Point sets are implemented by a combination of two-dimensional range trees
  99. [Wi85, Lu78] and Voronoi diagrams.  Operations insert, lookup, del\_item, del 
  100. take time $O(\log^2 n)$, key, inf, empty, size, change\_inf take time $O(1)$, 
  101. and clear takes time $O(n\log n)$. A range\_search operation takes time
  102. $O(k+\log^2 n)$, where $k$ is the size of the returned list. A nearest\_neighbor
  103. query takes time $O(n^2)$, if it follows any update operation (insert or
  104. delete) and $O(log n)$ otherwise. Here $n$ is the current size of the 
  105. point set. The space requirement is $O(n^2)$.
  106.  
  107.